package Graph;

import java.util.*;


public class GraphLoopTest {
    private Map<String, List<String>> graph = new HashMap<String, List<String>>();


    public void initGraphData() {

        graph.put("a", Arrays.asList("b", "c","d"));
        graph.put("b", Arrays.asList("a","e","f"));
        graph.put("c", Arrays.asList("a","g","b"));
        graph.put("d", Arrays.asList("a", "i"));
        graph.put("e", Arrays.asList("b","c"));
        graph.put("f", Arrays.asList("b"));
        graph.put("g", Arrays.asList("c"));
        graph.put("h", Arrays.asList("c"));
        graph.put("i", Arrays.asList("d"));
    }


    private Queue<String> queue = new LinkedList<String>();
    private Map<String, Boolean> status = new HashMap<String, Boolean>();

    public void BFSSearch(String startPoint) {

        queue.add(startPoint);
        status.put(startPoint, false);
        bfsLoop();
    }

    private void bfsLoop() {

        String currentQueueHeader = queue.poll();
        status.put(currentQueueHeader, true);
        System.out.println(currentQueueHeader);

        List<String> neighborPoints = graph.get(currentQueueHeader);
        for (String poinit : neighborPoints) {
            if (!status.getOrDefault(poinit, false)) {
                if (queue.contains(poinit)) continue;
                queue.add(poinit);
                status.put(poinit, false);
            }
        }
        if (!queue.isEmpty()) {
            bfsLoop();
        }
    }


    private Stack<String> stack = new Stack<String>();
    public void DFSSearch(String startPoint) {
        stack.push(startPoint);
        status.put(startPoint, true);
        dfsLoop();
    }

    private void dfsLoop() {
        if(stack.empty()){
            return;
        }

        String stackTopPoint = stack.peek();

        List<String> neighborPoints = graph.get(stackTopPoint);
        for (String point : neighborPoints) {
            if (!status.getOrDefault(point, false)) {
                stack.push(point);
                status.put(point, true);
                dfsLoop();
            }
        }
        String popPoint =  stack.pop();
        System.out.println(popPoint);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("选择深度（1）,广度遍历（2）:");
        int choose = scan.nextInt();
        GraphLoopTest test = new GraphLoopTest();
        test.initGraphData();
        if(choose==1){
            System.out.println("深度优先遍历： ");
            test.DFSSearch("a");}
        if(choose==2){
            System.out.println("广度优先遍历 ：");
            test.BFSSearch("a");}

    }
}
